"""面试题 08.12. 八皇后  https://leetcode.cn/problems/eight-queens-lcci/description/"""


# 方法1：基于集合的回溯算法
# 链接：https://leetcode.cn/problems/eight-queens-lcci/solutions/403802/ba-huang-hou-by-leetcode-solution/
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # 定义一个函数，用于生成棋盘，实际上调用到这个函数的时候表示已经遍历到最后一行了，这里对回溯函数处理完成的各个数据进行整合
        def generateBoard():
            # 这里的棋盘本质上是一个一维的列表（一种解决方案，所以的解决方案是存储在solutions里面的），只不过每个小列表里面存储的是其中的一行
            board = list()
            for i in range(n):
                # 将皇后放在第i列，这里的 queens[i] 是存储皇后的列号（下标行的值列）
                # 在每一行里面位于queens[i] 存储的列号的位置放置Q
                row[queens[i]] = "Q"
                # 每行把皇后放置完毕后，把这一行添加到棋盘里面（成为一个小列表）
                board.append("".join(row))

                # 这里是一个清理，由于当前行的皇后的棋盘已经加入了，这里清理一下后面的在找其他的解决方案的时候就可以继续重新用了
                row[queens[i]] = "."
            return board

        # 定义回溯函数，这里回溯函数相当于是对每一行的皇后进行处理
        def backtrack(row: int):
            # 如果当前行是第n行，说明已经找到了一个解决方案
            if row == n:
                board = generateBoard()
                solutions.append(board)
            else:
                # 遍历当前行的所有列
                for i in range(n):
                    # 如果该位置已经被用过，或者在主对角线、副对角线被用过，则跳过
                    # 这里的row - i 是主对角线位置的性质，在这个线上的每个位置的row - i 的值都是一样的，副对角线的位置同理，每个位置都是row + i 的值都是一样的
                    if (
                        (i in columns)
                        or (row - i in diagonal1)
                        or (row + i in diagonal2)
                    ):
                        continue

                    # 否则到这里第某行的皇后的列数设置为 i
                    queens[row] = i

                    # 设置好后刷新一下三个字典
                    columns.add(i)
                    diagonal1.add(row - i)
                    diagonal2.add(row + i)

                    # 递归调用回溯函数，处理下一行
                    # 这里如果当前行的每一列都是不能放置的，上面就直接continue了，所以这里不会继续递归，开始返回，由于是还没有走到最后，说明并没有找到一个可行的解决方案，这里后面在递归返回位置后需要对三个字典进行回溯(清理掉)，然后不断返回，不断清理，直到某个可能的位置继续开始递归（注意这里不是直接返回到最开始，而是找到某个可以的位置继续循环遍历）
                    backtrack(row + 1)

                    # 回溯操作，撤销皇后放置
                    columns.remove(i)
                    diagonal1.remove(row - i)
                    diagonal2.remove(row + i)

        # 这里相当于是数据对象
        # 需要传回的解决方案
        solutions = list()
        # 存储皇后放置的列号，初始化-1表示当前的皇后没有放置
        # 这里很巧妙的利用了下标作为行号，存储的值作为列号
        queens = [-1] * n
        # 三个字典表示分别记录每一列以及两个方向上面的斜线上面是不是已经有皇后
        # 这里由于我们每次只是对一行操作，所以行上面的肯定是没有皇后的，只需要看其他三个方向即可
        columns = set()
        diagonal1 = set()
        diagonal2 = set()
        # 这个row是每一行的棋盘，在上面的generateBoard里面用于构建总体的棋盘
        row = ["."] * n
        # 从回溯算法开始，这里每行不断的去找皇后的位置，直到找到一个解决方案就调用生成棋盘的函数，
        backtrack(0)
        # 这里返回的是所有的解决方案，以小列表的方式返回
        return solutions


# 方法二：基于位运算的回溯
# https://leetcode.cn/problems/eight-queens-lcci/solutions/403802/ba-huang-hou-by-leetcode-solution/
class Solution:
    """这种优化主要是对空间复杂度进行优化，优化的变量是存储三个检测当前位置上是否有皇后的三个字典，"""

    def solveNQueens(self, n: int) -> List[List[str]]:
        def generateBoard():
            board = list()
            for i in range(n):
                row[queens[i]] = "Q"
                board.append("".join(row))
                row[queens[i]] = "."
            return board

        def solve(row: int, columns: int, diagonals1: int, diagonals2: int):
            if row == n:
                board = generateBoard()
                solutions.append(board)
            else:
                availablePositions = ((1 << n) - 1) & (
                    ~(columns | diagonals1 | diagonals2)
                )
                while availablePositions:
                    position = availablePositions & (-availablePositions)
                    availablePositions = availablePositions & (availablePositions - 1)
                    column = bin(position - 1).count("1")
                    queens[row] = column
                    solve(
                        row + 1,
                        columns | position,
                        (diagonals1 | position) << 1,
                        (diagonals2 | position) >> 1,
                    )

        solutions = list()
        queens = [-1] * n
        row = ["."] * n
        solve(0, 0, 0, 0)
        return solutions
